The process of creating very-large-scale integrated (VLSI) circuit designs typically includes a structured sequence of steps. In an initial step, a VLSI circuit designer creates a computerized representation of a VLSI circuit design using a computerized tool. In the ensuing steps, the designer generates a series of subsequent representations using specialized tools including synthesis tools, optimization tools, and place-and-route tools. The designer might also generate a new representation manually using a computerized editing tool.
In general, each representation in the series describes the design at a different level of abstraction. It is common for the initial representation to describe the design at a high level of abstraction, and for each subsequent representation to describe the design at a respective lower level of abstraction. For example, the initial representation may describe the design at the register-transfer level (RTL), a subsequent representation may describe the design at the gate-level, and a subsequent representation from that may describe the design at the transistor-level. The process culminates with the generation of a database containing geometric detail of masks that will be used to fabricate the design.
A circuit design representation describes a design as a set of basic components that are connected together. Due to the size and complexity of VLSI circuit designs, it is a common practice for the designer to group components together in subsets called module definitions (or modules). A module defines an arrangement of components and other modules, and can be instantiated more than once in a representation. That is, the designer creates a module once to define an arrangement of elements, and uses instances of that module to represent specific portions of the design. Many hardware description languages (HDLs) support this hierarchical manner of design description. Designs are written as a set of module definitions. Computerized tools that read such designs can construct the full hierarchical representation of the design from the module definitions. In the full hierarchical representation, each element of the design has a unique representation.
To insure that no unintended changes are introduced into a newly generated representation, particularly when manual modifications have been made, the designer applies a computerized verification tool to the newly generated representation and a predecessor. The verification tool verifies that particular design aspects such as functional behaviors are preserved from representation to representation. This verifying process commonly is referred to as xe2x80x9cdesign verification.xe2x80x9d An example of such a tool is Design VERIFYer (TM), which is marketed by Chrysalis Symbolic Design, Inc. of Billerica, Mass. Design VERIFYer verifies behavior preservation between first and second representations of a circuit design by finding matches between logic signals represented by the representations, and by comparing the logic functions driving the signals.
The signals of each representation are identifiable by signal name. If two representations are at the same level of abstraction (e.g., before and after optimization at the gate level) the signal names typically are kept the same. Design VERIFYer has a xe2x80x9cname basedxe2x80x9d mode that finds matches between signals of different representations by matching signal names.
If two representations are at different levels of abstraction (e.g., before and after RTL-to-gate synthesis) the signal names typically are changed in some uniform manner. A designer may use a signal name mapping tool that performs xe2x80x9crule-based signal matchingxe2x80x9d prior to running the design verification tool to account for such changes. The signal name matching tool refers to each signal in one representation by signal name, i.e., by a character string. The character string is a series of subnames separated by a delimiter xe2x80x9c.xe2x80x9d for example. The last subname in the series uniquely identifies a signal within a particular hierarchical element of the representation. The portion of the series up to but not including the last subname uniquely identifies the hierarchical element within the representation that contains the signal.
Hierarchy information and signal information are blended into one by flattening the hierarchy and maintaining the information implicitly as path prefixes in signal names. Then both kinds of mapping can be performed by considering only signal names.
Hierarchy can be understood as an organization or ordering of signals. As long as one can find the proper hierarchical organization of signals in both design representations and find at least part of the true relationship between the two hierarchies, one can use the information to improve verification performance. A hierarchical representation is a complete description of the design and manages the complexity of the design. A hierarchical description of a design consists of a set of modules, one of which is designated as the top module. Modules contain two kinds of elements: objects and instances. An object is a basic component of a design domain (for example, a signal in an electronic design). An instance is a use of a module. Instances thus define how modules are related. For example, consider the following two modules. Module P contains two objects (signal a and signal b), and module Q ontains one object (signal c) and two instances of module P (p1 and p2).
module P
signal a;
signal b;
end module.
module Q
signal c;
instance p1 of P;
instance p2 of P;
end module.
Each element in a hierarchical description has a unique path name. This name is constructed as a concatenation of the instance names along the path from the root to the element plus the name of the element itself, with some delimiter (for example, the period character) between each name. For example, if module Q is the xe2x80x9ctopxe2x80x9d module then the following elements can be identified by name:
top (instance of Q)
top.c (signal)
top.p1 (instance)
top.p1.a (signal)
top.p1.b (signal)
top.p2 (instance)
top.p2.a (signal)
top.p2.b (signal)
As discussed in U.S. provisional application Serial No. 60/085,041, different expressions of hierarchy result over the evolution of a design. Early in the design history there will be explicit hierarchy in the design representation, expressed using design language constructs. Later in the history after the design representation is flattened or made non-hierarchical, there will be implicit hierarchy encoded in the signal names. Still later, explicit hierarchy might be added to a flat design representation via grouping.
It is useful to map hierarchies for purposes of comparing design representations. By way of an example, by default, Design VERIFYer maps instances with the same names. This is done using the following default rule:
map_hierarchy_rule A . . . %s B . . . %1s;
For each pair of instances that match a rule, a Map_Hierarchy is created to map the instances together. Hierarchy mapping is done in a top-down fashion. That is, when an instance is considered, all of the instances in the path to that instance will already have been considered. This is important so that xe2x80x98 . . . xe2x80x99 (xe2x80x9cmatch at each level of hierarchyxe2x80x9d) will work properly.
For example, suppose the design representations contained the following instances:
A.ctrl B.ctrl
A.ctrl.counter B.ctrl.counter
A.ctrl.decoder B.ctrl.decoder
The rule above works as follows.
Roots A and B are mapped;
Adhering to top-down ordering, the instance A.ctrl will be considered first. This instance will be matched by A . . . %s: the A . . . matches the path A and the %s matches the string xe2x80x9cctrlxe2x80x9d. Given this match, the instance B.ctrl will be matched by B . . . .%1s. The B . . . means xe2x80x9cmatch the equivalent path as was matched in the A design,xe2x80x9d i.e., B and the %1s means xe2x80x9cmatch the same string as was matched by the first %sxe2x80x9d, i.e., the string xe2x80x9cctrlxe2x80x9d. Since a pair of instances has been found, a mapping is created:
map_hierarchy A.ctrl B.ctrl;
Now that A.ctrl has been considered, the instances below it can be considered, so A.ctrl.counter is considered next. This instance will be matched by A . . . %s: the A . . . matches the path A.ctrl and the %s matches the string xe2x80x9ccounterxe2x80x9d. Given this match, the instance B.ctrl.counter will be matched by B . . . %1s. The B . . . means xe2x80x9cmatch the equivalent path as was matched in the A design,xe2x80x9d i.e., B.ctrl (note that the mapping of A.ctrl and B.ctrl had to happen first for this to work), and the %1s matches xe2x80x9ccounterxe2x80x9d, producing:
map_hierarchy A.ctrl.counter B.ctrl.counter;
This process continues, mapping all of the instances in the two hierarchies.
If instance names are not the same in the two design representations but they are related in a systematic way, then rules can be used to map the hierarchies. For example, the suffixxe2x80x9c_instxe2x80x9d might be added to all instances in the second or subsequent design representation:
A.ctrl B.ctrl_inst
A.ctrl.counter B.ctrl_inst.counter_inst
A.ctrl.decoder B.ctrl_inst.decoder_inst
All these instances can be mapped using one rule:
map_hierarchy_rule A . . . %s B . . . %1s_inst;
For example, A . . . %s will match A.ctrl, B . . . %1s_inst will match B.ctrl_inst. and the instances will be mapped together. Then A . . . %s will match A.ctrl.counter, B . . . %1s_inst will match B.ctrl_inst.counter_inst (since A.ctrl and B.ctrl_inst have already been mapped), and those instances will be mapped together.
Continuing this example, suppose that the signal names have not changed. Then the following rules will map the hierarchies and all the signals:
map_hierarchy_rule A . . . %s B. . . %1s_inst;
map_signal rule A . . . %s B . . . %1s.
Hierarchy mapping can be used to simplify signal mapping rules and the design verification process. Applicants take advantage of the recognition that hierarchy information is similar to signal information as both are structural: both are identified by name, and both can be mapped to show how two design representations are related.
According to the present invention, a hierarchical structure for a non-hierarchical, non-ordered representation of a circuit design having components defined by component names including hierarchial path information, is generated from a reference hierarchical structure and a set of rules. Subsequently, the newly generated hierarchical structure is populated by the design components defined by component names and a set of delimiters to provide a hierarchy representation corresponding to the subject non-hierarchical representation. This hierarchy representation enables comparison between the reference hierarchical structure and the new hierarchy representation to determine equivalence of the circuit designs associated with the new generated and reference hierarchical structure.
In a preferred embodiment, the present invention includes a generation step wherein a hierarchy from a reference design hierarchy is read, and used to create a template hierarchy for a revised representation of the design, and a population step wherein the components defined by component or signal names of the revised design representation are placed in the generated hierarchy for the revised design representation. The generation step of the present invention produces a mapping of the hierarchical elements of the reference and generated hierarchies. This mapping may be used to determine the equivalence of the reference and revised designs representations.
Further, in a preferred embodiment the hierarchy generation technique is integrated in a design verification system. The design verification system includes memory that stores a main working program, a first hierarchy of elements as the first representation of the design, a second non-hierarchical representation of elements as the second representation of the design and a plurality of generation rules. As the processing circuitry executes the program, the processing circuitry performs the following operations: a read operation that reads the elements of the first hierarchical representation from the memory; a generate operation that generates a second template hierarchy for the second representation according to the elements of the first representation and a plurality of generation rules; a populate operation that completes the template hierarchy by placing elements or components defined by the non-hierarchical component names of the second representation in the template hierarchy, and a compare operation that compares the first representation with the second representation according to the first hierarchy and generated second template hierarchy. The result of a comparison between the first and second representations indicates whether the first representation matches with the second representation. The integration of the hierarchy generation technique in the design verification system enables operations such as the generate, populate and compare operations to be well adapted to each other.